package com.wtgroup.demo.mianshi.算法.排序2305;

import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Tools;

import java.util.Arrays;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/1 15:30
 */
public class MergeSort {
    public static void main(String[] args) {
        Judger.of(() -> {
            int[] nums = RandomUtil.randomArray((int) (Math.random() * 1000 + 1), 0, 100);
            // int[] nums = {2, 9, 11, 17, 24};
            int[] copy1 = Arrays.copyOf(nums, nums.length);
            new M2_哨兵().mergeSort(copy1);

            int[] copy2 = Arrays.copyOf(nums, nums.length);
            Arrays.sort(copy2);

            if (!Tools.equals(copy1, copy2)) {
                Tools.printArray(nums);
                Tools.printArray(copy1);
                Tools.printArray(copy2);
                return false;
            }
            return true;
        }).setIterCount(1000).start().print();
    }

    // 推荐
    static class M1 {
        public void mergeSort(int[] arr) {
            mergeSort(arr, 0, arr.length - 1);
        }

        private void mergeSort(int[] arr, int left, int right) {
            if (left >= right) {
                return;
            }

            int mid = (left + right) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // 两种合并思路
            // 中间数组. M2.1 左右先复制出来, 比较回填; M2.2 比较备份到临时数组, 完事了回填

            merge(arr, left, right);

        }

        private void merge(int[] arr, int left, int right) {
            // 复制出左右两个局部有序数组
            int mid = (left + right) / 2;
            int[] leftPrt = new int[mid - left + 1];
            int[] rightPrt = new int[right - mid];
            for (int i = 0, j = left; i < leftPrt.length; ) {
                leftPrt[i++] = arr[j++];
            }
            for (int i = 0, j = mid + 1; i < rightPrt.length; ) {
                rightPrt[i++] = arr[j++];
            }

            // 比较, 回填

            int l = 0, r = 0, arrix = left;
            while (l < leftPrt.length && r < rightPrt.length) {
                if (leftPrt[l] <= rightPrt[r]) {
                    arr[arrix++] = leftPrt[l++];
                } else {
                    arr[arrix++] = rightPrt[r++];
                }
            }
            while (l < leftPrt.length) {
                arr[arrix++] = leftPrt[l++];
            }
            while (r < rightPrt.length) {
                arr[arrix++] = rightPrt[r++];
            }
        }
    }

    static class M2_哨兵 {
        public void mergeSort(int[] arr) {
            mergeSort(arr, 0, arr.length - 1);
        }

        private void mergeSort(int[] arr, int left, int right) {
            if (left >= right) {
                return;
            }

            int mid = (left + right) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // 两种合并思路
            // 中间数组. M2.1 左右先复制出来, 比较回填; M2.2 比较备份到临时数组, 完事了回填

            merge(arr, left, right);

        }

        private void merge(int[] arr, int left, int right) {
            // 复制出左右两个局部有序数组
            int mid = (left + right) / 2;
            int[] leftPrt = new int[mid - left + 1 + 1];
            int[] rightPrt = new int[right - mid + 1];
            for (int i = 0, j = left; i < leftPrt.length - 1; ) {
                leftPrt[i++] = arr[j++];
            }
            leftPrt[leftPrt.length - 1] = Integer.MAX_VALUE;
            for (int i = 0, j = mid + 1; i < rightPrt.length - 1; ) {
                rightPrt[i++] = arr[j++];
            }
            rightPrt[rightPrt.length - 1] = Integer.MAX_VALUE;

            // 比较, 回填

            int l = 0, r = 0, arrix = left;
            while (arrix <= right) {
                // 右侧下标跑得快, 提前到'哨兵', 往后一直 true, 即一直往后复制左侧的; else里提前到左侧哨兵同理
                if (leftPrt[l] <= rightPrt[r]) {
                    arr[arrix++] = leftPrt[l++];
                } else {
                    arr[arrix++] = rightPrt[r++];
                }
            }
        }
    }
}
